package com.qezhhnjy.leetcode.question.tree;

import com.qezhhnjy.leetcode.question.Generate;
import com.qezhhnjy.leetcode.entity.TreeNode;

import java.util.Arrays;


/**
 * @author zhaoyangfu - 2020/12/6 21:17
 * 给定有序数组: [-10,-3,0,5,9],
 * <p>
 * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
 * <p>
 *       0
 *      / \
 *    -3   9
 *   /   /
 * -10  5
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-height-tree-lcci
 */
public class MinHeightTree implements Generate<int[], TreeNode> {

    @Override
    public TreeNode generate(int[] nums) {
        int len = nums.length;
        if (len == 0) return null;
        TreeNode root = new TreeNode(nums[len / 2]);

        // from 包含，to不包含
        root.setLeft(generate(Arrays.copyOfRange(nums, 0, len / 2)));

        root.setRight(generate(Arrays.copyOfRange(nums, len / 2 + 1, len)));

        return root;
    }

    public static void main(String[] args) {
        System.out.println(new MinHeightTree().generate(new int[]{-10, -3, 0, 5, 9}));
    }

}
